{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #珠宝的最高价值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: jewelleryValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #珠宝的最高价值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有一个记作二维矩阵 <code>frame</code> 的珠宝架，其中 <code>frame[i][j]</code> 为该位置珠宝的价值。拿取珠宝的规则为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>只能从架子的左上角开始拿珠宝</li>\n",
    "\t<li>每次可以移动到右侧或下侧的相邻位置</li>\n",
    "\t<li>到达珠宝架子的右下角时，停止拿取</li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 <code>frame = [[0]]</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> frame = [[1,3,1],[1,5,1],[4,2,1]]\n",
    "<strong>输出:</strong> <code>12\n",
    "</code><strong>解释:</strong> 路径 1→3→5→2→1 可以拿到最高价值的珠宝</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt; frame.length &lt;= 200</code></li>\n",
    "\t<li><code>0 &lt; frame[0].length &lt;= 200</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [li-wu-de-zui-da-jie-zhi-lcof](https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [li-wu-de-zui-da-jie-zhi-lcof](https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m,n = len(frame),len(frame[0])\n",
    "        dp = [0] * n\n",
    "        for l in frame:\n",
    "            for i,x in enumerate(l):\n",
    "                if i != 0: dp[i] = max(dp[i],dp[i-1])\n",
    "                dp[i] += x\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m, n = len(frame), len(frame[0])\n",
    "        #  用于记录上一行每一位置能获取的最大价值\n",
    "        pre_row = [0] * n\n",
    "\n",
    "        for j in range(n):\n",
    "            if j == 0:\n",
    "                pre_row[j] = frame[0][j]\n",
    "            else:\n",
    "                pre_row[j] = pre_row[j-1] + frame[0][j]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            cur_row = [0] * n\n",
    "            cur_row[0] = pre_row[0] + frame[i][0]\n",
    "            for j in range(1, n):\n",
    "                cur_row[j] = max(cur_row[j-1], pre_row[j]) + frame[i][j]\n",
    "            pre_row = cur_row\n",
    "\n",
    "        return pre_row[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        n=len(frame[0])\n",
    "        m=len(frame)\n",
    "        dp=[0]*n\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[j]=max(dp[max(j-1,0)],dp[j])+frame[i][j]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        for i, row in enumerate(frame):\n",
    "            if i == 0:\n",
    "                dp = row \n",
    "                for j in range(1, len(dp)):\n",
    "                    dp[j] += dp[j-1]\n",
    "            else:\n",
    "                for j, x in enumerate(row):\n",
    "                    if j == 0:\n",
    "                        dp[0] += x \n",
    "                    else:\n",
    "                        dp[j] = max(dp[j], dp[j-1]) + x\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, grid: List[List[int]]) -> int:\n",
    "        if grid is None: return 0\n",
    "        M = len(grid)\n",
    "        N = len(grid[0])\n",
    "        dp = [0 for _ in range(N+1)]\n",
    "        for i in range(1, M+1):\n",
    "            for j in range(1, N+1):\n",
    "                dp[j] = max(dp[j-1]+grid[i-1][j-1], dp[j]+grid[i-1][j-1])\n",
    "        return dp[N]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        M,N = len(frame),len(frame[0])\n",
    "        dp = [[0]*(N+1)]*(M+1)\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])+frame[i][j]\n",
    "        return dp[M][N]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m = len(frame)\n",
    "        n = len(frame[0])\n",
    "        f = [0]*(n+1)\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                f[j] = frame[i-1][j-1] +max (f[j],f[j-1])\n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# f(i,j) = max(f(i-1,j),f(i,j-1)) +a[i][j]\n",
    "# f(i,j) = 0 if i<0 or j<0\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        maxvals=[0 for x in frame[0]]\n",
    "        for listi in frame:\n",
    "            j=0\n",
    "            for vj in listi:\n",
    "                maxvals[j] = self.fmaxv(maxvals, j) +vj\n",
    "                j=j+1\n",
    "\n",
    "        return maxvals[-1]\n",
    "    \n",
    "    def fmaxv(self,maxvals, j):\n",
    "        leftv= maxvals[j-1] if (j>0) else 0\n",
    "        upperv=maxvals[j]\n",
    "        return leftv if (leftv >upperv) else upperv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        dp = [0] * (len(frame[0]) + 1)\n",
    "        for i in range(len(frame)):\n",
    "            for j in range(1, len(frame[0]) + 1):\n",
    "                dp[j] = max(dp[j - 1], dp[j]) + frame[i][j - 1]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        dp = [[0] * len(frame[0])] * len(frame)\n",
    "        dp[0][0] = frame[0][0]\n",
    "        for i in range(0, len(frame)):\n",
    "            for j in range(0, len(frame[0])):\n",
    "                if i == 0 and j == 0: continue\n",
    "                elif i == 0:\n",
    "                    dp[i][j] = dp[i][j-1] + frame[i][j]\n",
    "                elif j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] + frame[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + frame[i][j]\n",
    "        return dp[len(frame)-1][len(frame[0])-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        dp = [0] * (len(frame[0]) + 1)\n",
    "        for i in range(len(frame)):\n",
    "            for j in range(len(frame[0])):\n",
    "                dp[j+1] = max(dp[j], dp[j+1]) + frame[i][j]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m = len(frame)\n",
    "        n = len(frame[0])\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i: int, j: int) -> int:\n",
    "        #     if i >= m or j >= n:\n",
    "        #         return 0\n",
    "        #     return frame[i][j] + max(dfs(i+1, j), dfs(i, j+1))\n",
    "\n",
    "        # return dfs(0, 0)\n",
    "\n",
    "        # dp = [0]*n\n",
    "        # for i in range(m-1, -1, -1):\n",
    "        #     dp[-1] += frame[i][-1]\n",
    "        #     for j in range(n-2, -1, -1):\n",
    "        #         dp[j] = frame[i][j] + max(dp[j], dp[j+1])\n",
    "\n",
    "        # return dp[0]\n",
    "\n",
    "        dp = [0] * (n+1)\n",
    "        for row in frame:\n",
    "            for j, x in enumerate(row):\n",
    "                dp[j+1] = x + max(dp[j+1], dp[j])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        frame.insert(0, [0]*len(frame[0]))\n",
    "        for term in frame:\n",
    "            term.insert(0, 0)\n",
    "        for i in range(1, len(frame)):\n",
    "            for j in range(1, len(frame[0])):\n",
    "                frame[i][j] += max(frame[i][j-1], frame[i-1][j])\n",
    "        return frame[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        for i in range(len(frame)):\n",
    "            for j in range(len(frame[0])):\n",
    "                if i==0 and j==0:\n",
    "                    continue\n",
    "                if i == 0:\n",
    "                    frame[i][j] = frame[i][j]+frame[i][j-1]\n",
    "                elif j == 0:\n",
    "                    frame[i][j] = frame[i-1][j]+frame[i][j]\n",
    "                else:\n",
    "                    frame[i][j] = max(frame[i-1][j],frame[i][j-1])+frame[i][j]\n",
    "        return frame[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        for i in range(len(frame)):\n",
    "            for j in range(len(frame[0])):\n",
    "                if i == 0 and j == 0: continue\n",
    "                elif i == 0:\n",
    "                    frame[i][j]+=max(frame[i][j-1],0)\n",
    "                elif j == 0:\n",
    "                    frame[i][j]+=max(frame[i-1][j],0)\n",
    "                else:\n",
    "                    frame[i][j]+=max(frame[i][j-1], frame[i-1][j])\n",
    "        return frame[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        for i in range(len(frame)):\n",
    "            for j in range(len(frame[i])):\n",
    "                if i == j == 0:\n",
    "                    continue\n",
    "                elif i == 0:\n",
    "                    frame[i][j] += frame[i][j-1]\n",
    "                elif j == 0:\n",
    "                    frame[i][j] += frame[i-1][j]\n",
    "                else:\n",
    "                    frame[i][j] += max(frame[i-1][j], frame[i][j-1])\n",
    "        return frame[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        mov = ((0,1),(1,0))\n",
    "        len1 = len(frame) - 1\n",
    "        len2 = len(frame[0]) - 1\n",
    "        tmpval1 = len1 + len2\n",
    "        while tmpval1 >= 0 :\n",
    "            #print(tmpval1, frame)\n",
    "            for x in range(tmpval1+1) :\n",
    "                y = tmpval1 - x\n",
    "                if x < 0 or x > len1 or y < 0 or y > len2 :\n",
    "                    continue\n",
    "                tmplist1 = []\n",
    "                for m in mov :\n",
    "                    x1, y1 = x + m[0], y + m[1]\n",
    "                    if x1 < 0 or x1 > len1 or y1 < 0 or y1 > len2 :\n",
    "                        tmplist1.append(0)\n",
    "                    else :\n",
    "                        tmplist1.append(frame[x1][y1])\n",
    "                frame[x][y] += max(tmplist1)\n",
    "            tmpval1 -= 1\n",
    "\n",
    "        return frame[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m, n = len(frame), len(frame[0])\n",
    "        for j in range(1, n): # 初始化第一行\n",
    "            frame[0][j] += frame[0][j - 1]\n",
    "        for i in range(1, m): # 初始化第一列\n",
    "            frame[i][0] += frame[i - 1][0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                frame[i][j] += max(frame[i][j - 1], frame[i - 1][j])\n",
    "        return frame[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        #dp[i][j]:走到i，j位置最高可以拿到价值dp[i][j]价值的内容\n",
    "        #dp=[[0 for _ in range(len(frame[1])+1)] for _ in range(len(frame[0])+1)]\n",
    "        for i in range(len(frame)):\n",
    "            for j in range(len(frame[0])):\n",
    "                if i == 0 and j == 0: continue\n",
    "                if i == 0: frame[i][j] += frame[i][j - 1]\n",
    "                elif j == 0: frame[i][j] += frame[i - 1][j]\n",
    "                else:frame[i][j]=max(frame[i][j]+frame[i-1][j],frame[i][j]+frame[i][j-1])\n",
    "                #dp[i][j]=max(dp[i-1][j]+frame[i-1][j-1],dp[j-1][i]+frame[i-1][j-1])\n",
    "\n",
    "        return frame[-1][-1]\n",
    "\n",
    "# class Solution:\n",
    "#     def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "#         #dp[i][j]:走到i，j位置最高可以拿到价值dp[i][j]价值的内容\n",
    "#         if len(frame)==1:\n",
    "#             return frame[0][0]\n",
    "#         dp=[[0 for _ in range(len(frame[1])+1)] for _ in range(len(frame[0])+1)]\n",
    "#         for i in range(1,len(frame[1])+1):\n",
    "#             for j in range(1,len(frame[1])+1):\n",
    "#                 dp[i][j]=max(dp[i-1][j]+frame[i-1][j-1],dp[i][j-1]+frame[i-1][j-1])\n",
    "#         print(dp)\n",
    "#         return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        for i in range(1, len(frame)):\n",
    "            frame[i][0] += frame[i-1][0]\n",
    "        for i in range(1, len(frame[0])):\n",
    "            frame[0][i] += frame[0][i-1]\n",
    "        for i in range(1, len(frame)):\n",
    "            for j in range(1, len(frame[0])):\n",
    "                frame[i][j] += max(frame[i-1][j], frame[i][j-1])\n",
    "        return frame[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        for i in range(len(frame)):\n",
    "            for j in range(len(frame[0])):\n",
    "                if i == 0 and j == 0: continue\n",
    "                if i == 0:\n",
    "                    frame[i][j] += frame[i][j - 1]\n",
    "                elif j == 0:\n",
    "                    frame[i][j] += frame[i - 1][j]\n",
    "                else:\n",
    "                    frame[i][j] += max(frame[i][j - 1], frame[i - 1][j])\n",
    "        return frame[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m, n = len(frame), len(frame[0])\n",
    "        for j in range(1, n):\n",
    "            frame[0][j] += frame[0][j-1]\n",
    "        for i in range(1, m):\n",
    "            frame[i][0] += frame[i-1][0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                frame[i][j] += max(frame[i-1][j], frame[i][j-1])\n",
    "        return frame[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m,n=len(frame),len(frame[0])\n",
    "        for j in range(1,n):\n",
    "            frame[0][j]+=frame[0][j-1]\n",
    "        for i in range(1,m):\n",
    "            frame[i][0]+=frame[i-1][0]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                frame[i][j]+=max(frame[i][j-1],frame[i-1][j])\n",
    "        return frame[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m, n = len(frame), len(frame[0])\n",
    "        for j in range(1, n):\n",
    "            frame[0][j] += frame[0][j-1]\n",
    "        for i in range(1, m):\n",
    "            frame[i][0] += frame[i-1][0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                frame[i][j] += max(frame[i][j-1], frame[i-1][j])\n",
    "        return frame[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m, n = len(frame), len(frame[0])\n",
    "        for i in range(1, m):\n",
    "            frame[i][0] += frame[i-1][0]\n",
    "        for i in range(1, n):\n",
    "            frame[0][i] += frame[0][i-1]\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                frame[i][j] += max(frame[i-1][j], frame[i][j-1])\n",
    "        return frame[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        for i in range(len(frame)):\n",
    "            for j in range(len(frame[i])):\n",
    "                if i==0 and j==0:\n",
    "                    continue\n",
    "                elif i==0:\n",
    "                    frame[i][j]+=frame[i][j-1]\n",
    "                elif j==0:\n",
    "                    frame[i][j]+=frame[i-1][j]\n",
    "                else:\n",
    "                    frame[i][j]+=max(frame[i][j-1],frame[i-1][j])\n",
    "        return frame[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m=len(frame)\n",
    "        n=len(frame[0])\n",
    "        dp=[[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        if len(frame)==1 and len(frame[0])==1:\n",
    "            return frame[0][0]\n",
    "        row = len(frame)\n",
    "        col = len(frame[0])\n",
    "        if row==1:\n",
    "            return sum (frame[0])\n",
    "        if col ==1:\n",
    "             return sum (frame)\n",
    "        dp = [[0] * col for _ in range(row)]\n",
    "        dp[0][0]=frame[0][0]\n",
    "        for i in range(0,row):\n",
    "            for j in range(0,col):\n",
    "                if i==0 and j!=0:\n",
    "                    dp[i][j]=dp[i][j-1]+frame[i][j]\n",
    "                elif j==0:\n",
    "                    dp[i][j]=dp[i-1][j]+frame[i][j]\n",
    "                else:\n",
    "                    dp[i][j]=frame[i][j]+max(dp[i-1][j],dp[i][j-1])\n",
    "        return dp[-1][-1]  \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        if not frame or not frame[0]:\n",
    "            return 0\n",
    "\n",
    "        rows, cols = len(frame), len(frame[0])\n",
    "\n",
    "        # 初始化dp数组\n",
    "        dp = [[0] * cols for _ in range(rows)]\n",
    "        dp[0][0] = frame[0][0]\n",
    "\n",
    "        # 初始化第一行和第一列\n",
    "        for i in range(1, rows):\n",
    "            dp[i][0] = dp[i-1][0] + frame[i][0]\n",
    "\n",
    "        for j in range(1, cols):\n",
    "            dp[0][j] = dp[0][j-1] + frame[0][j]\n",
    "\n",
    "        # 动态规划计算路径的最大和\n",
    "        for i in range(1, rows):\n",
    "            for j in range(1, cols):\n",
    "                dp[i][j] = frame[i][j] + max(dp[i-1][j], dp[i][j-1])\n",
    "\n",
    "        return dp[rows-1][cols-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        # dfs超时\n",
    "        # if not frame:\n",
    "        #     return 0\n",
    "\n",
    "        # self.res = 0\n",
    "        # m = len(frame)\n",
    "        # n = len(frame[0])\n",
    "\n",
    "        # def dfs(i,j,cur):\n",
    "        #     # 到达终点\n",
    "        #     if i == m - 1 and j == n - 1:\n",
    "        #         cur += frame[i][j]\n",
    "        #         self.res = max(self.res,cur)\n",
    "        #         return\n",
    "            \n",
    "        #     if i == m or j== n:\n",
    "        #         return\n",
    "            \n",
    "        #     cur += frame[i][j]\n",
    "        #     dfs(i + 1,j,cur)\n",
    "        #     dfs(i,j + 1,cur)\n",
    "\n",
    "        # dfs(0,0,0)\n",
    "        # return self.res\n",
    "            \n",
    "        # 动态规划\n",
    "        if not frame:\n",
    "            return 0\n",
    "\n",
    "        m = len(frame)\n",
    "        n = len(frame[0])\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        dp[0][0] = frame[0][0]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i - 1 >= 0:\n",
    "                    a = dp[i - 1][j]\n",
    "                else:\n",
    "                    a = 0\n",
    "                if j - 1 >= 0:\n",
    "                    b = dp[i][j - 1]\n",
    "                else:\n",
    "                    b = 0\n",
    "                dp[i][j] = max(a,b) + frame[i][j]\n",
    "        \n",
    "        return dp[m - 1][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        # dfs超时\n",
    "        # if not frame:\n",
    "        #     return 0\n",
    "\n",
    "        # self.res = 0\n",
    "        # m = len(frame)\n",
    "        # n = len(frame[0])\n",
    "\n",
    "        # def dfs(i,j,cur):\n",
    "        #     # 到达终点\n",
    "        #     if i == m - 1 and j == n - 1:\n",
    "        #         cur += frame[i][j]\n",
    "        #         self.res = max(self.res,cur)\n",
    "        #         return\n",
    "            \n",
    "        #     if i == m or j== n:\n",
    "        #         return\n",
    "            \n",
    "        #     cur += frame[i][j]\n",
    "        #     dfs(i + 1,j,cur)\n",
    "        #     dfs(i,j + 1,cur)\n",
    "\n",
    "        # dfs(0,0,0)\n",
    "        # return self.res\n",
    "            \n",
    "        # 动态规划\n",
    "        if not frame:\n",
    "            return 0\n",
    "\n",
    "        m = len(frame)\n",
    "        n = len(frame[0])\n",
    "        dp = [[0] * (n) for _ in range(m)]\n",
    "        dp[0][0] = frame[0][0]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i - 1 >= 0:\n",
    "                    a = dp[i - 1][j]\n",
    "                else:\n",
    "                    a = 0\n",
    "                if j - 1 >= 0:\n",
    "                    b = dp[i][j - 1]\n",
    "                else:\n",
    "                    b = 0\n",
    "                dp[i][j] = max(a,b) + frame[i][j]\n",
    "        \n",
    "        return dp[m - 1][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]):\n",
    "        m, n = len(frame), len(frame[0])\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0] = frame[0][0]\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = dp[i-1][0] + frame[i][0]\n",
    "        for i in range(1, n):\n",
    "            dp[0][i] = dp[0][i-1] + frame[0][i]\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + frame[i][j]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m = len(frame)\n",
    "        n = len(frame[0])\n",
    "        f = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                f[i][j]= frame[i-1][j-1] + max(f[i-1][j],f[i][j-1])\n",
    "        return f[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i > 0:\n",
    "                    f[i][j] = max(f[i][j], f[i - 1][j])\n",
    "                if j > 0:\n",
    "                    f[i][j] = max(f[i][j], f[i][j - 1])\n",
    "                f[i][j] += grid[i][j]\n",
    "        \n",
    "        return f[m - 1][n - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        # if frame[0][0] == 0:\n",
    "        #     return 0\n",
    "        row, col = len(frame), len(frame[0])\n",
    "        dp = [[0]*col for _ in range(row)]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if i==0 and j==0:\n",
    "                    dp[i][j] = frame[i][j]\n",
    "                elif i==0:\n",
    "                    dp[i][j] = dp[i][j-1] + frame[i][j]\n",
    "                elif j ==0:\n",
    "                    dp[i][j] = dp[i-1][j] + frame[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])+ frame[i][j]\n",
    "        return dp[row-1][col-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        \n",
    "        dp = [[0]*len(frame[0]) for _ in range(len(frame))]\n",
    "        dp[0][0] = frame[0][0]\n",
    "        for j in range(1,len(frame[0])):\n",
    "            dp[0][j] = dp[0][j-1] + frame[0][j]\n",
    "        for i in range(1,len(frame)):\n",
    "            dp[i][0] = dp[i-1][0] + frame[i][0]\n",
    "        for i in range(1,len(frame)):\n",
    "            for j in range(1,len(frame[0])):\n",
    "                dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + frame[i][j]\n",
    "        \n",
    "        return dp[len(frame)-1][len(frame[0])-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m = len(frame)\n",
    "        n = len(frame[0])\n",
    "        temp = [0 for i in range(n)]\n",
    "        frame.insert(0,temp)\n",
    "        for i in range(m+1):\n",
    "            frame[i].insert(0,0)\n",
    "        \n",
    "        d = [[0 for i in range(n+1)] for j in range(m+1)]\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                d1 = d[j-1][i]\n",
    "                d2 = d[j][i-1]\n",
    "                d[j][i] = max(d1,d2)+frame[j][i]\n",
    "        return d[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m,n=len(frame),len(frame[0])\n",
    "        dp=[[0 for i in range(n)] for j in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 and j==0:\n",
    "                    dp[i][j]=frame[0][0]\n",
    "                elif i==0:\n",
    "                    dp[i][j] = dp[i][j-1]+frame[i][j]\n",
    "                elif j==0:\n",
    "                    dp[i][j]=dp[i-1][j]+frame[i][j]\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i][j]\n",
    "        for i in dp:\n",
    "            print(i)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m = len(frame)\n",
    "        n = len(frame[0])\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i][j] = max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1]\n",
    "        return dp[m][n]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        if not frame:\n",
    "            return 0\n",
    "        ROW, COL = len(frame), len(frame[0])\n",
    "        pad = [[0 for _ in range(COL+1)] for _ in range(ROW+1)]\n",
    "        for i in range(ROW):\n",
    "            for j in range(COL):\n",
    "                pad[i][j] = frame[i][j]\n",
    "        for i in range(ROW - 1, -1, -1):\n",
    "            for j in range(COL - 1, -1, -1):\n",
    "                pad[i][j] += max(pad[i + 1][j], pad[i][j + 1])\n",
    "        return pad[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m,n=len(frame),len(frame[0])\n",
    "        dp=[[0 for _ in range(n+1)]for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m,n = len(frame), len(frame[0])\n",
    "\n",
    "        for i in range(1, n):\n",
    "            frame[0][i] += frame[0][i-1]\n",
    "        for j in range(1, m):\n",
    "            frame[j][0] += frame[j-1][0]\n",
    "\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                frame[i][j] += max(frame[i-1][j],frame[i][j-1])\n",
    "        print(frame)\n",
    "        return frame[-1][-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        for i in range(len(frame)):\n",
    "            for j in range(len(frame[0])):\n",
    "                if i==j==0:\n",
    "                    frame[i][j]=frame[i][j]\n",
    "                elif i == 0:\n",
    "                    frame[i][j] = max(frame[i][j-1]+frame[i][j],frame[i][j])\n",
    "                elif j == 0:\n",
    "                    frame[i][j] = max(frame[i-1][j]+frame[i][j],frame[i][j])\n",
    "                else:\n",
    "                    frame[i][j] = max(frame[i-1][j],frame[i][j-1]) + frame[i][j] \n",
    "\n",
    "        print(frame)\n",
    "        return frame[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        if len(frame)==0:\n",
    "            return 0\n",
    "\n",
    "        memo = [[0]*len(frame[0]) for _ in range(len(frame))]\n",
    "\n",
    "\n",
    "        def dp(m,n):\n",
    "            if m==0 and n==0:\n",
    "                return frame[0][0]\n",
    "            if m<0 or n<0:\n",
    "                return 0\n",
    "            \n",
    "            if memo[m][n]>0:\n",
    "                return memo[m][n]\n",
    "            \n",
    "            memo[m][n] = max(dp(m-1,n),dp(m,n-1))+frame[m][n]\n",
    "            return memo[m][n]\n",
    "        \n",
    "        m,n = len(frame)-1,len(frame[0])-1\n",
    "\n",
    "        return dp(m,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m , n = len(frame), len(frame[0])\n",
    "        dp = [[0] *n for _ in range(m)]\n",
    "        print(dp)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[i][j] = frame[i][j]+ max(dp[i-1][j],dp[i][j-1])\n",
    "                print(f'dp[{i}][{j}]={dp[i][j]} = frame[{i}][{j}] = {frame[i][j]}+ max(dp[{i-1}][{j}]={dp[i-1][j]},dp[{i}][{j-1}]={dp[i][j-1]})')\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m = len(frame)\n",
    "        n = len(frame[0])\n",
    "\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0][0] = frame[0][0]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 and j != 0:\n",
    "                    dp[i][j] = dp[i][j - 1] + frame[i][j]\n",
    "                if j == 0 and i != 0:\n",
    "                    dp[i][j] = dp[i - 1][j] + frame[i][j]\n",
    "                if i != 0 and j != 0:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j]\n",
    "        \n",
    "        print(dp)\n",
    "        return dp[-1][-1]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jewelleryValue(self, frame: List[List[int]]) -> int:\n",
    "        m = len(frame)\n",
    "        n = len(frame[0])\n",
    "\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0][0] = frame[0][0]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 and j != 0:\n",
    "                    dp[i][j] = dp[i][j - 1] + frame[i][j]\n",
    "                if j == 0 and i != 0:\n",
    "                    dp[i][j] = dp[i - 1][j] + frame[i][j]\n",
    "                if i != 0 and j != 0:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j]\n",
    "        \n",
    "        print(dp)\n",
    "        return dp[-1][-1]\n",
    "                \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
